package Sort.sort2020_2;

/**
 * 希尔排序
 * 从小到大
 * @author: leiwenkang
 * @date: 2020/5/23
 * @time: 18:17
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] array = {3,8,4,6,7,2,5,9,1};
        sort(array);
        for (int i = 0; i < array.length; i++){
            System.out.print(array[i]);
            System.out.print(" ");
        }
    }

    public static void sort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int increment = array.length;
        while (increment > 1) {
            increment = increment / 3 + 1;
            for (int i = increment; i < array.length; i += increment) {
                if (array[i] < array[i - increment]) {
                    int value = array[i];
                    //比value大的值均右移
                    int j;
                    for (j = i - increment; j >= 0 && array[j] >= value; j -= increment) {
                        array[j + increment] = array[j];
                    }
                    array[j + increment] = value;
                }
            }

        }

    }
}
